282. Expression Add Operators

https://leetcode.com/problems/expression-add-operators/

題目解釋

題目會給一組全部都是數字的字串，還有一個數字target ，請用+、-、*組出能得到target的算式，並回傳所有可能結果

example

解法

今天的題目一看就知道要用backtracking，但我還是寫不出來就是了

所以今天我就來分享看懂解答的過程，所以先上程式碼吧

程式碼

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        
        def backtracking(index, prev, curr, n, path):

            if index == len(num):
                
                if target == n and curr == 0:
                    ans.append(''.join(path[1:]))
                return 
            
            curr = curr * 10 + int(num[index])
            
            if curr > 0: #一大坨東西
                backtracking(index+1, prev, curr, n, path)
            
            # 加
            backtracking(index+1, curr, 0, n + curr, path + ['+', str(curr)])

            if path:
                #減
                backtracking(index+1, -curr, 0, n - curr, path + ['-', str(curr)])
                
                #乘
                backtracking(index+1, prev * curr, 0, n - prev + prev * curr, path + ['*', str(curr)])

            
        
        ans = []
        backtracking(0, 0, 0, 0, [])
        
        return ans

那我們就重頭開始吧!

1. 首先，我們先定義一個backtracking 函數，裡面5個參數代表目前字串位置、前一個數字、現在數字、算式累積結果、目前的算式

def backtracking(index, prev, curr, n, path)

2. backtracking都會有個中斷條件，要嘛發現不能做了，要嘛做完大功告成

而這題的結束且有結果的條件有3個:

• 我們的指標已經到尾端了
• 我們手上的東西都處理完了
• 算式的結果符合題目要求

if index == len(num):

    if target == n and curr == 0:
        ans.append(''.join(path[1:]))
    return 

3. 接著，我們先來看現在數字的計算

curr = curr * 10 + int(num[index])

算式裡的curr * 10是因為字串裡的數字不只能當成個位數，也能組成二位數、三位數...

如果curr = 0的話，就是把數字當個位數處理

4. 這部分就是專門處理組合多位數的，要求大於0的原因我覺得很難講，只能請大家印出來自行體會

if curr > 0: #一大坨東西
    backtracking(index+1, prev, curr, n, path)

5. 接著，我們看相加的部分

backtracking(index+1, curr, 0, n + curr, path + ['+', str(curr)])

prev的欄位放curr是因為我們目前的數字對下個backtracking的數字來說是先前數字；curr的欄位放0則可以當成是一個新開始的算式；累積的結果加上去就好

6. 相減的部分也差不多，不過在那之前有個if path的判斷式，可以想成是要有東西可以減才成執行

backtracking(index+1, -curr, 0, n - curr, path + ['-', str(curr)])

7. 乘法看起來比較不一樣，在累積結果的部分出現減法是因為乘號的優先度較高，感覺如下面這張圖
   
   backtracking(index+1, prev * curr, 0, n - prev + prev * curr, path + ['*', str(curr)])

8. 連我自己都看不懂我在打什麼了，建議還是自己動手拿紙筆模擬一遍好了

閒聊

今天的題目是這個月第一次用到回朔法，結果就直接來hard題目了

如果有人和我一樣想不出來只能看解答的

看完後可以試解這題來看看自己是否已理解解答